// 368. 最大整除子集
// AC: https://leetcode.cn/problems/largest-divisible-subset/submissions/620251371/

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        vector<int> dp(n,1);
        int mas=1,mav=nums[0];
        for(int i=1;i<n;++i){
            for(int j=0;j<i;++j){
                if(nums[i]%nums[j]==0)
                    dp[i]=max(dp[i],dp[j]+1);
            }
            if(dp[i]>mas){
                mas=dp[i];
                mav=nums[i];
            }
        }
        vector<int> ans;
        for(int i=n-1;i>=0&&mas;--i){
            if(dp[i]==mas&&mav%nums[i]==0){
                ans.push_back(nums[i]);
                mav=nums[i];
                mas--;
            }
        }
        return ans;
    }
};